package a;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class _3层序最短路径 {

    int openLock(String[] deadends, String target) {

        //初始化 que、vis
        Set<String> visited = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        int step = 0;
        q.offer("0000");
        visited.add("0000");
        //障碍
        Set<String> deads = new HashSet<>();
        for (String s : deadends) deads.add(s);

        while (!q.isEmpty()) {
            int sz = q.size();
            //分层step oldSz
            for (int i = 0; i < sz; i++) {
                String cur = q.poll();

                //障碍con
                if (deads.contains(cur)) continue;
                //终点return
                if (cur.equals(target)) return step;

                //预判(i+1)符合再bfs(i+1)
                for (int j = 0; j < 4; j++) {
                    String up = plusOne(cur, j);
                    if (!visited.contains(up)) {
                        q.offer(up);
                        visited.add(up);
                    }
                    String down = minusOne(cur, j);
                    if (!visited.contains(down)) {
                        q.offer(down);
                        visited.add(down);
                    }
                }
            }
            //每层oldSZ
            step++;
        }

        //没找到
        return -1;
    }

    private String minusOne(String cur, int j) {
        return null;
    }
    private String plusOne(String cur, int j) {
        return null;
    }
}
